时间复杂度 O(n^{2/3})，空间复杂度 O(n^{1/3}  log^3(n))
调用 prime_pi(n) 返回 = n 的质数数量（不包含1）
namespace MeisselLehmer {
  using ll = long long;
  ll prime_pi(const ll N) {
  if (N = 1) {
    return 0;
  }
  if (N == 2) {
    return 1;
  }
  auto div = [&](ll n, ll d) - int {
    return (double)n  d;
  };
  auto half = [&](int n) - int {
    return (n - 1)  1;
  };
  const int v = sqrtl(N);
  int s = (v + 1)  2;
  vectorint smalls(s), roughs(s); 
  vectorll larges(s);
  for (int i = 0; i  s; ++i) {
    smalls[i] = i;
    roughs[i] = (i  1  1);
    larges[i] = (N  roughs[i] - 1)  2;
  } 
  vectorbool skip(v + 1);
  int pc = 0;
  for (int p = 3; p = v; p += 2) {
    if (!skip[p]) {
      int q = p  p;
      if ((ll)(q)  q  N) {
        break;
      }
      skip[p] = true;
      for (int i = q; i = v; i += 2  p) {
        skip[i] = true;
      }
      int ns = 0;
      for (int k = 0; k  s; ++k) {
        int i = roughs[k];
        if (skip[i]) {
          continue;
        }
        ll d = (ll)(i)  p;
        larges[ns] = larges[k] - (d = v  larges[smalls[d  1] - pc]  smalls[half(div(N, d))]) + pc;
        roughs[ns++] = i;
      }
      s = ns;
      for (int i = half(v), j = ((v  p) - 1)  1; j = p; j -= 2) {
        int c = smalls[j  1] - pc;
        for (int e = (j  p)  1; i = e; --i) {
          smalls[i] -= c;
        }
      }
      ++pc;
    }
  }
  larges[0] += (ll)(s + 2  (pc - 1))  (s - 1)  2;
  for (int k = 1; k  s; ++k) {
    larges[0] -= larges[k];
  }
  for (int l = 1; l  s; ++l) {
    int q = roughs[l];
    ll M = N  q;
    int e = smalls[half(M  q)] - pc;
    if (e  l + 1) {
      break;
    }
    ll t = 0;
    for (int k = l + 1; k = e; ++k) {
      t += smalls[half(div(M, roughs[k]))];
    }
    larges[0] += t - (ll)(e - l)  (pc + l - 1);
  }
  return larges[0] + 1;
}
}